1. Field of the Invention
This invention relates to a bus controller or arbiter for controlling access to the bus of a computer system.
2. Description of the Related Art
Computers are becoming a more integral part of everyone""s lives with each passing day. There is an ever-present demand for more efficient and faster-operating computers. The speed at which a computer operates is partially dependent on the rate at which data can be accessed by the different devices (e.g., disk drives, modems, etc.) attached to the computer.
Every computer includes a bus which serves as a conduit for the transfer of information between the central processing unit (CPU) of the computer and the various peripherals. Typically, the computer also includes a bus controller (often called an arbiter) for controlling which devices may access the bus, and in what order. A typical arbiter assigns priority values to each device depending on the requirements of the device. For instance, an interactive graphics adapter which is receiving video images over a modem or a network will have high priority because it must have access to the bus at all times, or valuable data will be lost. If the graphics adapter must wait to gain access to the CPU, the data which is transmitted during the waiting period may be lost. Such access interruptions can cause the video image being transmitted to appear jerky and unclear. A device such as a disk drive, however, is a relatively low priority device, since the data is stored in a tangible medium and can be re-accessed at any time.
FIG. 1 shows an exemplary prior art computer system 15 including a conventional arbiter 40. It should be noted that the computer system 15 is merely one conventional way to implement a computer system with an arbiter, various other system configurations are known to those skilled in the art. A bus 10 having address, data and control information connects a CPU 20 with a memory 30 and the arbiter 40. The bus 10 is also connected to various peripherals 50, 60 (e.g., disk drives, CD-ROM drives, modems, etc.) which are used in conjunction with the computer system 15. In the computer system 15 shown in FIG. 1, there are two peripherals 50, 60 designated as xe2x80x9cDevice 1xe2x80x9d and xe2x80x9cDevice 2xe2x80x9d, respectively. Each peripheral 50, 60 includes bus request lines R1, R2, bus grant lines G1, G2, and input/output (I/O) lines connected to the bus 10 destined for the arbiter 40. When a peripheral (e.g., 50) requires access to the bus 10, it sends out a signal on its bus request line (R1) to the arbiter 40 (via the bus 10). The arbiter 40 includes circuitry (not shown) which decides if the request will be granted, and at what time. When the request is granted, the arbiter 40 sends out a xe2x80x9cgrantxe2x80x9d signal, via the bus 10, on the grant line (G1), letting the device (50) known that the bus 10 is ready to transfer or receive its information. The device (50) then transmits or receives the information over its associated I/O line. When transmitting information, the data travels from the device to the bus 10, and then to the information receiver (e.g., CPU 20). When receiving information, the data travels from the transmitter (e.g., CPU 20), over the bus 10 and over the I/O line to the peripheral (in some cases, the CPU 20 itself may act as a peripheral). As stated above, most conventional arbiters assign priorities to each peripheral device based on the arbitration scheme and the general importance of the peripheral. For instance, if xe2x80x9cDevice 1xe2x80x9d (FIG. 2) were a audio sampling device such as a microphone, and xe2x80x9cDevice 2xe2x80x9d were a floppy disk drive, xe2x80x9cDevice 1xe2x80x9d would have a high priority because there is a higher likelihood of data loss. However, most conventional arbiters do not assign different arbitration schemes to periodic requests as opposed to aperiodic (i.e., one time) requests.
Some devices, such as CD-ROM drives, require periodic accessing of the bus. In other words, they need to access the bus many times (e.g., three times) over a specified time period (e.g., 10 xcexcs). These devices are often referred to as periodic devices. Other examples of periodic devices include: modems and real-time video and audio samplers. The problem encountered with periodic devices is that in the time period between accesses, the bus controller may grant control of the bus to another device because it believes that the periodic device has completed its use of the bus. Therefore, each time the periodic device needs access to the bus it must make another request. Sometimes, if another device has already begun use of the bus, the periodic request may be den i ed by the arbiter, thereby slowing down the accessing process for the periodic device or causing the data transmitted to or from the periodic device to be delayed, queued or lost. The conventional process used for allowing periodic devices access to the computer bus is inefficient because the bus grant/request procedure may need to be repeated numerous times in a short period for the same periodic device.
Kelley et al., in U.S. Pat. No. 5,758,105, describe a method and apparatus for arbitrating periodic and aperiodic requests. The ""105 patent describes an arbiter which contains two arbitration algorithms, one for periodic requests and one for aperiodic requests. The arbiter decides whether the device making the bus request is an aperiodic or a periodic device, and executes the proper algorithm accordingly. As can be seen from FIG. 3 of the ""105 patent, the arbiter assigns each device connected to the arbiter a certain amount of time on the bus depending upon the requirements of the device. The ""105 patent does not describe the periodic bus allocation algorithm, nor does it discuss the effect of arbitrary device rates on the operation of the bus. When rates are arbitrary, no synchronous scheme can guarantee conflict free access to the bus for all devices for an indefinite period of time. Requests of two devices with arbitrary rates (not multiple of each other) will conflict at some time leading to queuing at one or both devices. The queuing of information introduces data delays into the system. The arbiter of the ""105 patent does not take into account the queue length of each device trying to gain access to the bus and thus, is sub-optimal.
Accordingly, there is currently a need for bus controller that operates at very high speeds and that dynamically allocates space on a bus between both periodic and aperiodic devices, recognizes periodic devices and grants these devices control of the bus in a manner that minimizes data delays everywhere in the system by estimating queue lengths of the devices (or other performance metrics of interest).
The present invention is an arbiter which efficiently achieves controlled delays for all devices on the bus, whether periodic or aperiodic. The arbiter divides devices into two categories, periodic and aperiodic. When a request is made the information is relayed to a processor which decides whether to grant or deny the request. A service log located within the arbiter keeps track of important information relating to the requests, such as rate (for periodic requests), data transfer size, device queue length, etc. A time line memory located within the arbiter contains fixed sized entries of bus access service durations for the devices. The arbiter uses the queue length information to determine when a device should be granted access to the bus and uses the time line memory to allocate and grant bus service time to the device. For aperiodic requests, the arbiter consults the time line memory to locate an empty slot to service the request. For periodic requests, the arbiter uses information from the log in conjunction with the time line memory to allocate as many timeslots as it can until it detects a potential conflict (or other criteria are met). The arbiter uses these allocations to issue anticipatory grants to the requesting device. Thus, the arbiter effectively minimizes the queue length and reduces the data delay experienced at each device.